package com.company.algo.simpleOrhard;

import java.util.Arrays;

public class maximum_product_of_three_numbers {
    /*有负数的情况，寻找三个元素，使之相乘为最大值
    最大值的情况：
    1.两个最小元素都是负数，且与最大元素相乘
    2.三个最大元素相乘
    * */
    public int maximumProduct1(int[] nums) {
        Arrays.sort(nums);
        int len = nums.length;
        return Math.max(nums[0]*nums[1]*nums[len-1],
                nums[len-1]*nums[len-2]*nums[len-3]);
    }
    //线性扫描，避免排序
    public int maximumProduct(int[] nums) {
        int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
        int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;
        for(int x: nums){
            //找最小的两个值
            if(x<min1) {
                min2 = min1;    //此时第二小的值为第一小的值
                min1 = x;       //第一小的值更新
            }else if(x<min2){
                min2 =  x;
            }
            //找最大的三个值
            if(x > max1){
                max3 = max2;
                max2 = max1;
                max1 = x;
            }else if(x>max2){
                max3 = max2;
                max2 = x;
            }else if(x>max3){
                max3 = x;
            }
        }
        return Math.max(min1*min2*max1, max1*max2*max3);
    }
}
